package com.bascker.algorithm.practice.sliding_window.middle.find_repeated_dna_sequences;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution2 {

    public List<String> findRepeatedDnaSequences(String s) {
        // 处理非法数据
        if (null == s || s.length() < 10) {
            return new ArrayList<>();
        }

        int n = s.length();

        final Map<String, Integer> dict = new HashMap<>();

        final List<String> rs = new ArrayList<>();
        for (int i = 0; i <= n - 10; i ++) {
            // 固定窗口大小10
            String sub = s.substring(i, i + 10);
            // 计数
            dict.put(sub, dict.getOrDefault(sub, 0) + 1);

            // 计数后判断该序列是否重复
            if (dict.get(sub) > 1 && !rs.contains(sub)) {
                rs.add(sub);
            }
        }

        return rs;
    }

}
